package uk.ac.manchester.cs.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Undirected graph implementation
 * 
 * @author Pavel Klinov
 *
 * pklinov@cs.man.ac.uk, pklinov@clarkparsia.com
 * 
 * 27 Apr 2010
 */
public class GraphImpl<V, E> implements Graph<V, E> {

	private Map<V, Set<Edge<V, E>>> m_vertexMap = new HashMap<V, Set<Edge<V, E>>>();
	
	public boolean isDirected() {
		
		return false;
	}
	
	public Edge<V, E> addEdge(E object, V start, V end) {

		EdgeImpl<V, E> edge = null;
		
		if (null == (edge = findEdge( start, end ))) {
			
			edge = new EdgeImpl<V, E>(object, start, end);
			
			addVertex(start);
			addVertex(end);
			
			getIncidentEdges( start ).add( edge );
			getIncidentEdges( end ).add( edge );
		}
		
		return edge;
	}
	
	public Set<Edge<V, E>> getIncidentEdges(V vertex) {
		
		return m_vertexMap.get( vertex );
	}
	
	public void addVertex(V vertex) {

		if (!m_vertexMap.containsKey( vertex )) {
			
			m_vertexMap.put( vertex, new HashSet<Edge<V, E>>() );
		}
	}

	public Set<V> getAdjacentVertices(V vertex) {

		Set<Edge<V, E>> incidentEdges = getIncidentEdges( vertex );
		
		if (incidentEdges != null) {
			
			Set<V> neighbors = new HashSet<V>();
			
			for (Edge<V, E> incident : incidentEdges) {
				
				neighbors.add( incident.getStart() );
				neighbors.add( incident.getEnd() );
			}
			
			neighbors.remove( vertex );
			
			return neighbors;
		}
	
		return null;
	}

	public Set<V> getVertices() {
 
		return m_vertexMap.keySet();
	}

	public void removeVertex(V vertex) {

		Set<Edge<V, E>> incidentEdges = getIncidentEdges( vertex );
		
		if (incidentEdges != null) {
		
			for (Edge<V, E> incident : incidentEdges) {
				
				V otherEnd = vertex.equals( incident.getStart() )
															? incident.getEnd()
															: incident.getStart();
	
				getIncidentEdges( otherEnd ).remove( incident );
			}
			
			m_vertexMap.remove( vertex );
		}
	}

	public void removeEdge(Edge<V, E> edge) {
		
		getIncidentEdges( edge.getStart() ).remove( edge );
		getIncidentEdges( edge.getEnd() ).remove( edge );
	}
	
	public EdgeImpl<V, E> findEdge(V start, V end) {
		
		EdgeImpl<V, E> edge = null;
		
		for (Edge<V, E> incident : getIncidentEdges( start )) {
			
			if ((incident.getEnd().equals( end ) && incident.getStart().equals( start ))
					|| (incident.getStart().equals( end ) && incident.getEnd().equals( start ))) {
				
				edge = (EdgeImpl<V, E>)incident;
				
				break;
			}
		}
		
		return edge;
	}
}
